题面传送门：P16491 [GKS 2014 #D] GBus count
题目大意
给出 Gbus 的运营范围，求特定位置的 Gbus 覆盖数量。
思路讲解
首先想到暴力的思路，每输入一条线路就给这条线路服务的所有城市答案 ，时间复杂度约 ，能过。
观察题面，每条线路覆盖的范围已给出，最好能快速求变化量。差分与前缀和的方法更优。
代码实现
从差分到前缀和还原
根据差分的基本思路，只需在左端点和右端点之后一个位置对数组进行修改。
注意：本题的城市数量只与 的范围有关，故下方求前缀和时循环到 。
for(int i=1;i<=n;i++){ cin>>a[i]>>b[i]; s[a[i]]++; s[b[i]+1]--;}for(int i=1;i<=5005;i++){ s[i]=s[i-1]+s[i];}完整代码
#include<bits/stdc++.h>using namespace std;int t,n,a[505],b[505],p,c,s[5005];int main(){ cin>>t; for(int z=1;z<=t;z++){ memset(s,0,sizeof(s));//多测不清空，_____ cout<<"Case #"<<z<<": "; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]>>b[i]; s[a[i]]++; s[b[i]+1]--; } for(int i=1;i<=5005;i++){ s[i]=s[i-1]+s[i]; } cin>>p; for(int i=1;i<=p;i++){ cin>>c; cout<<s[c]<<' '; } cout<<endl; } return 0;}